package sysu.el.graph.undi.algor;


import java.util.ArrayList;

import sysu.el.array.ints.ArrInt;
import sysu.el.array.type.ArrType;
import sysu.el.graph.GraphConstants;
import sysu.el.graph.Path;
import sysu.el.graph.tree.FatherTreeTopo;
import sysu.el.graph.undi.UndiGT;
import sysu.el.tuple.TupleIntValue;

public class RingSearcher extends MSTCreator{

	/** 
	 * Memo Tech
	 * 
	 */
	public FatherTreeTopo[] treeList = null;	
	
	/**
	 * Functor Results
	 */
	public TupleIntValue[][] nodeIDRings;
	public int [][] nodeIDRings2;
	
	public RingSearcher(UndiGT g) {
		super(g);
		treeList = new FatherTreeTopo[g.getNodeNum()];
		path = new Path(g.getNodeNum());
		rings = new ArrType<TupleIntValue>(g.getNodeNum());
		rings2 = new ArrInt(g.getNodeNum()); 
		nodeIDRings = new TupleIntValue[g.getNodeNum()][];
	}
	
	/**
	 * Algorithm Data
	 */
	ArrType<TupleIntValue> rings;
	ArrInt rings2;
	Path path;
	
	public int calNodeToRootLen(FatherTreeTopo tree, int node){
		int fa = node;
		int sum = 0;
		while (fa != tree.root){
			int child = tree.fa[fa];
			sum += graph.getW(fa, child);
			fa = child;
		}
		return sum;
	}
	
	/**
	 * Key Node means if the node is taken away, the subtrees will 
	 * be separated.
	 * 
	 * @param root
	 * @return
	 */
	public boolean isRootKeyNode(int root){
		TupleIntValue[] rings = this.getRings(root);
		if (rings.length == 0)
			return true;
		return false;
	}
	
	public int [] category;
	
	/**
	 * O(N)
	 * @param newMST
	 * @param root
	 */
	public void tagSubTree(FatherTreeTopo newMST, int root){
		category = new int[graph.getNodeNum()];
		this.isVisited.reset();
		int rootChildren[] = this.tree.adjNodes[root].list;
		
		category[root] = -1;
		this.isVisited.setVisited(root);
		
		for (int i=rootChildren.length-1; i>0; --i){// n-1
			this.queue.add(rootChildren[i]);
			while (queue.isNotEmpty()){
				int h = queue.forward();
				int list[] = this.tree.adjNodes[h].list;
//				int list[] = this.graph.getList(h);
				for (int j=list.length-1; j>=0; --j){
					if (this.isVisited.isVisited(list[j]))
						continue;
					queue.add(list[j]);
					this.isVisited.setVisited(list[j]);
					category[list[j]] = i;
				}
			}
		}
	}
	
	public int[] getCategory(int root){
		if (category[root] == -1)
			return category;
		else{
			this.tagSubTree(this.getTree(root), root);
		}
		return category;
	}
	
	/**
	 * Algorithms Data
	 * SideEffect Data: category, the divided graph;
	 * @param root
	 * @return 0 means no ring find, but very possible it exist
	 * If TupleIntValue.length equals zero, that also means it is a tree type.
	 */
	
	// SideEffect
	// make sure it is a tree, so it is connected.
	public TupleIntValue[] getRings(int root){
		if (this.nodeIDRings[root] != null)
			return this.nodeIDRings[root];
		
		FatherTreeTopo newMST = this.getTree(root);
		this.tagSubTree(newMST, root);
		
		this.rings.reset();
		for (int i=0; i<graph.getNodeNum(); ++i){
			if (i == root) continue;
			for (int j=i+1; j<graph.getNodeNum(); ++j){
				// Here just suggests one situation: root and its children
//				if ((newMST.fa[i] == j) || (newMST.fa[j] == i))
				if ((j == root)) continue;
				if ((category[i] != category[j])&&(graph.getW(i, j) != GraphConstants.NULL_EDGE)){
					int v = this.calNodeToRootLen(newMST, i) 
						+ this.calNodeToRootLen(newMST, j) + graph.getW(i, j);
					rings.add(new TupleIntValue(i, j, v));
				}
			}
		}
		
		rings2.reset();
		for (int i=0; i<graph.getNodeNum(); ++i)
			if (i!=root){
				if (graph.getW(i, root) != GraphConstants.NULL_EDGE)
					rings2.add(i);
			}
		
		this.nodeIDRings[root] = rings.toArray();
		this.nodeIDRings2[root] = rings2.toArray();
		return this.nodeIDRings[root];
	}
	
	/**
	 * Amortized already with Memo Technology
	 */
	public FatherTreeTopo getTree(int root){
		if (this.treeList[root] != null)
			return this.treeList[root]; 
		this.treeList[root] = super.getTree(root);
		return this.treeList[root];
	}
	
}

